#include<iostream>
using namespace std;
#include<vector>
#include<string>
class Solution {
public:
    string path;
    vector<string> ans;
    int dot = 3, n;
    void dfs(string& s, int start) {
        if (start >= n)
            return;
        if (dot == 0) {
            string now = s.substr(start);
            if (now[0] == '0') {
                if (now.size() > 1)
                    return;
                path += now;
                ans.push_back(path);
                path.pop_back();
                return;
            }
            if (now.size() > 3 || atoi(now.c_str()) > 255)
                return;
            path += now;
            ans.push_back(path);
            for (int i = 0; i < now.size(); ++i)
                path.pop_back();
            return;
        }
        --dot;
        if (s[start] == '0') {
            path += "0.";
            dfs(s, start + 1);
            path.pop_back();
            path.pop_back();
        }
        else {
            for (int i = start; i < n; ++i) {
                string now = s.substr(start, i - start + 1);
                if (atoi(now.c_str()) > 255)
                    break;
                path += now;
                path += '.';
                dfs(s, i + 1);
                for (int i = 0; i < now.size() + 1; ++i)
                    path.pop_back();
            }
        }
        ++dot;
        return;
    }
    vector<string> restoreIpAddresses(string s) {
        n = s.size();
        dfs(s, 0);
        return ans;
    }
};